package d_ch12;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;

import c_ch11.WeightedGraph;

public class BellmanFord {

    private WeightedGraph G;
    private int s;
    private int[] dis;
    private int[] pre;
    private boolean hasNegCycle = false;

    public BellmanFord(WeightedGraph G, int s){

        this.G = G;

        G.validateVertex(s);
        this.s = s;

        dis = new int[G.V()];
        Arrays.fill(dis, Integer.MAX_VALUE);
        dis[s] = 0;

        pre = new int[G.V()];
        Arrays.fill(pre, -1);
       
        /*	废话们：
     			明明思路一开始就理解了，但是为什么这里的实现逻辑懵了好久？ 我尝试了按着自己的逻辑去实现，发现不管是用队列还是什么都很难实现出来脑海里的逻辑；
            	其实，直接点到为止的表达出一个逻辑，一般就是这个逻辑最高效的实现了，但是这里按从s出发的思路很难形成一套固定的逻辑，所以没有表达出来。
            	这里的参考代码顺着一想，其实可以发现其结果是和想象中的一样的，只是"向上转型"了，虽不是最理想的逻辑，但能实现了，可能正是如此才会有SPFA算法吧；
         */
        for(int pass = 1; pass < G.V(); pass ++){         		  
        	for(int v = 0; v < G.V(); v ++)  //我既然很难精确控制步长增加时fore的次数，那向上转型行不行呢？遇到这种情况时，就应该这么想啊！我让每一轮步长都把所有顶点fore一遍，然后和s点连不起来的过滤掉就好了！这就是逆向思维啊！
        		for(int w: G.adj(v))  //必须基于有值的顶点来扩展；dis是上个步长留下来的；
                    if(dis[v] != Integer.MAX_VALUE &&  //dis[v]如果等于正无穷，就表示当前多走的一步和s是连不起来的，所以是无效值应该过滤掉，因为是从s出发的，步长不断增加时和s关联的顶点才会有值，其余的都是正无穷表示的不可达；
                       dis[v] + G.getWeight(v, w) < dis[w]){  //还是应该按照自己脑海里的思路，只是说这里的实现是逆向思维，但还是基于那个思想的；
                        dis[w] = dis[v] + G.getWeight(v, w);
                        pre[w] = v;
                    }
        }

        for(int v = 0; v < G.V(); v ++)    // 检测s所在连通分量的负权环；相同的逻辑，尝试再扩展一步；
            for(int w : G.adj(v))
                if(dis[v] != Integer.MAX_VALUE &&
                   dis[v] + G.getWeight(v, w) < dis[w]) {
                	hasNegCycle = true;
                	break;  //因为是无向图，连通分量里，只要有一个负权边，就可以反复横跳刷权值；
                }
    }

    public boolean hasNegativeCycle(){
        return hasNegCycle;
    }

    public boolean isConnectedTo(int v){
        G.validateVertex(v);
        return dis[v] != Integer.MAX_VALUE;
    }

    public int distTo(int v){
        G.validateVertex(v);
        if(hasNegCycle) throw new RuntimeException("exist negative cycle.");
        return dis[v];
    }

    public Iterable<Integer> path(int t){

        ArrayList<Integer> res = new ArrayList<Integer>();
        if(!isConnectedTo(t)) return res;

        int cur = t;
        while(cur != s){
            res.add(cur);
            cur = pre[cur];
        }
        res.add(s);

        Collections.reverse(res);
        return res;
    }

    static public void main(String[] args){
    	
//    	Iterable<Integer> test = Arrays.asList(1,2,5,7,9);
//    	System.out.println(test);
//    	Iterator<Integer> iterator = test.iterator();
//    	for(boolean hasNext=true; hasNext; hasNext = test.iterator().hasNext()){
//    		try{
//    			System.out.print(iterator.next());  //Iterator是迭代到抛异常为止，hasNext是跟着next(),直到next抛异常才返回false；
//    		}catch (Exception e) {
//			}
//    	}
    	
        WeightedGraph g = new WeightedGraph("g2_ch12.txt");
        BellmanFord bf = new BellmanFord(g, 0);
        if(!bf.hasNegativeCycle()){
            for(int v = 0; v < g.V(); v ++)
                System.out.print(bf.distTo(v) + " ");
            System.out.println();

            System.out.println(bf.path(1));
        }
        else
            System.out.println("exist negative cycle.");

        WeightedGraph g2 = new WeightedGraph("g2_ch12.txt");
        BellmanFord bf2 = new BellmanFord(g2, 0);
        if(!bf2.hasNegativeCycle()){
            for(int v = 0; v < g2.V(); v ++)
                System.out.print(bf2.distTo(v) + " ");
            System.out.println();
        }
        else
            System.out.println("exist negative cycle.");
    }
}
